home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 16002 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.2 KB
  1. Path: druid.borland.com!usenet
  2. From: pete@borland.com (Pete Becker)
  3. Newsgroups: comp.lang.c++,
  4. Subject: Re: Fastest Sorting Algorithm?
  5. Date: 9 Apr 1996 00:41:22 GMT
  6. Organization: Borland International
  7. Message-ID: <4kcbni$t2d@druid.borland.com>
  8. References: <DpAxtI.3w9@undergrad.math.uwaterloo.ca> <4k26jr$1cj@pipe10.nyc.pipeline.com>
  9. NNTP-Posting-Host: pbecker.borland.com
  10. Mime-Version: 1.0
  11. Content-Type: Text/Plain; charset=ISO-8859-1
  12. X-Newsreader: WinVN 0.99.5
  13.  
  14. In article <4k26jr$1cj@pipe10.nyc.pipeline.com>, digiulio@nyc.pipeline.com 
  15. says...
  16. >
  17. >2) If you are willing to sacrifice space for time, create an array of
  18. >pointers, which point to the records in the array.  Move the pointers in
  19. >the same manner as the quicksort  would move the records, and the pointers
  20. >would point to the records in sorted order.This would reduce the number of
  21. >swaps from O(n log n) to n. 
  22.  
  23. Close: it reduces the number of swaps of the underlying data to n. The total 
  24. number of swaps is still O(n log n), but the things being swapped that many 
  25. times are pointers. What this all reduces to is a linear decrease in execution 
  26. time, assuming that the underlying data objects are bigger than pointers.
  27.     -- Pete
  28.  
  29.